package algorithm;

public class LNode {
	
	public int data;
	public LNode pre; // 存储前一个节点的地址
	public LNode next; // 存储后一个节点的地址，存储格式为"algorithm.LNode@4e25154f"
	
	public LNode() {}
	
	public LNode(int data) {
		this.data = data;
	}
}

package algorithm;
import algorithm.LNode;

public class Doublecirclelist {	
	
	public LNode head;
		
	public Doublecirclelist() {
		this.head = new LNode();
		this.head.next = this.head;
		this.head.pre = this.head;
	}
	
	public boolean append(int node) {
		LNode Node = new LNode(node);
		// 新加节点与最后一个节点的关系
		this.head.pre.next = Node;
		Node.pre = this.head.pre;
		// 新加节点与头结点的关系
		Node.next = this.head;
		this.head.pre = Node;
		return true;
	}
	
	public boolean insert(int node, int index) {
		if (index > len() + 1 || index <= 0) {
            System.out.println("插入位置不合法！链表长度为：" + len());
		} else {
			LNode Node = new LNode(node);
			Node.data = node;
			if (this.head.pre == this.head) {
				Node.pre = this.head;
				Node.next = this.head;
				head.pre = Node;
				head.next = Node;
			} else if (index == len() + 1) {
				this.head.pre.next = Node;
				Node.pre = this.head.pre;
				Node.next = this.head;
				this.head.pre = Node;
			} else {
				LNode tmp = this.head;
				int count = 0;
				while (tmp.next != this.head) {
					count ++;
					if (count == index) {
						Node.pre = tmp;
						Node.next = tmp.next;
						tmp.next.pre = Node;
						tmp.next = Node;
					}
					tmp = tmp.next;
				}
			}
			return true;
		}
		return false;
	}
	
	public boolean delete(int index) {
		if (index > len() + 1 || index <= 0) {
            System.out.println("删除位置不合法！链表长度为：" + len());
		} else {
			LNode tmp = this.head;
			int count = 0;
			while (tmp.next != this.head) {
				tmp = tmp.next;
				count ++;
				if (index == count) {
					tmp.pre.next = tmp.next;
					tmp.next.pre = tmp.pre;
				}
			}
			return true;
		}
		return false;
	}
	
	public int get(int index) {
		if (index > len() + 1 || index <= 0) {
            System.out.println("位置不合法！链表长度为：" + len());
		} else {
			LNode tmp = this.head;
			int count = 0;
			while (tmp.next != this.head) {
				tmp = tmp.next;
				count ++;
				if (index == count) {
					return tmp.data;
				}
			}
		}
		return 0;
	}
	
	public boolean show() {
		LNode tmp = this.head;
		while (tmp.next != this.head) {
			tmp = tmp.next;
			System.out.printf("-%d-", tmp.data);
		}
		return true;
	}
	
	public int len() {
		int count = 0;
		LNode tmp = this.head;
		while (tmp.next != this.head) {
			count ++;
			tmp = tmp.next;
		}
		return count;
	}
	
	public static void main(String[] args) {
		Doublecirclelist list = new Doublecirclelist();
		list.insert(12, 1);
		list.append(11);
		list.append(10);
		list.insert(20, 3);
		list.delete(3);
		list.show();
		System.out.println("\n" + list.get(2));
	}

}
